МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національній університет "Львівська політехніка"
Дослідження роботи методів одновимірної оптимізації
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи №1
з курсу "Методи синтезу та оптимізації"
для студентів базового напряму 6.08.04 "Комп'ютерні науки"
ЗАТВЕРДЖЕНО
на засіданні кафедри САП
Протокол № 1 від 28.08 2008 р.
ЛЬВІВ 2008
Дослідження роботи методів одновимірної оптимізації. Методичні вказівки до лабораторної роботи №1 з курсу " Методи синтезу та оптимізації " для студентів базового напряму 6.08.04 "Комп'ютерні науки" /Укл. Андрійчук М. І., Теслюк В.М. - Львів: НУ "ЛП", 2008 р.
Укладачі: Андрійчук Михайло Іванович, к. ф.-м. н., доц.,
Теслюк Василь Миколайович, к.т.н., доц.
Відповідальний за випуск: Ткаченко С.П., к.т.н., доц.
Рецензенти: Каркульовський В. І., к.т.н., доц.,
Стех Ю.В, к.т.н., доц.
1. МЕТА РОБОТИ
Вивчити основні алгоритми розв’язку одновимірних оптимізаційних задач.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. Методи виключення інтервалів
Методи пошуку, які дозволяють визначити оптиум функції однієї змінної шляхом зменшення інтервалу пошуку, носять назву методів виключення інтервалів.
Усі методи одновимірної оптимізації базуються на припущенні, що цільова функція, в допустимій області принаймі володіє властивістю унімодальності, оскільки для унімодальної функції F(х) порівняння значень (F(х1) та F(х2))в двох різних точках (x1 і x2) інтервалу пошуку дозволяє визначити в якому із заданих підінтервалів точка оптиуму відсутня.
2.1.1. Правило виключення інтервалів.
Нехай F(х) унімодальна функція на відрізку [a, b], а її мінімум досягається в точці х*. Розглянемо точки x1 і x2, які розташовані а<x1<x2<b.
Якщо F(x1)>F(x2), то точка мінімуму F(х) не лежить в інтервалі (a, x1), тобто х*Є (x1, b).
Якщо F(x1)<F(x2), то точка мінімуму F(х) не лежить в інтервалі (x2, b), тобто х*Є (a, x2).
Це правило дозволяє реалізувати процедуру пошуку шляхом послідовного виключення частин початкового обмеженого інтервалу. Пошук завершується тоді, коли підінтервал, що залишився меншає до досить малих розмірів.
Основна перевага пошукових методів – вони базуються на обчисленні тільки значень функції і, отже, не вимагають виконання умови диференційованості і запису в аналітичному вигляді. Остання властивість особливо цінна при імітаційному моделюванні.
Процес застосування методів пошуку на основі виключення інтервалів включає два етапи:
етап встановлення границь інтервалу;
етап зменшення інтервалу.
2.1. 2. Метод поділу інтервалу пошуку наполовину.
Метод поділу інтервалу пошуку наполовину дозволяє зменшити інтервал пошуку наполовину при кожній ітерації.
Знайти F(х) на відрізку [a, b].
Крок 1. xm=(а+b)/2; L=b-a; обчислити F(xm).
Крок 2. x1=а+L/4; x2=b-L/4; обчислити F(x1) і F(x2).
Крок 3.
Якщо F(x1)<F(xm), то виключити (xm, b], тобто b=xm, xm=x1. Перейти до кроку 5.
Якщо F(x1)> F(xm), то перейти до кроку 4.
Крок 4.
Якщо F(x2)<F(xm), то виключити [a, xm), тобто а=xm, xm=x2. Перейти до кроку 5.
Якщо F(x2)> F(xm), то виключити [a, x1)][ і (x2, b], тобто а=x1, b=x2. Перейти до кроку 5.
Крок 5. L=b-a. ЯкщоL|е то закінчити пошук. В іншому випадку повернутися до кроку 2.
Як слідує з алгоритму, з кожних трьох значень цільової функції F(х), обчислених в інтервалі пошуку, надалі використовується тільки дві, а третя не дає додаткової інформації і надалі не використовується. У методі золотого січення цільова функція обчислюється в точках інтервалу, розташованих таким чином, щоб кожне обчислене значення цільової функції давало б нову корисну інформацію.
2.1. 3. Метод золотого січення.
Основна суть методу. Інтервал пошуку ділиться на дві рівні частини так, щоб відношення довжини великого відрізка до довжини всього інтервалу було таке, що дорівнює відношенню
=. Враховуючи, що z1+z2=z, будемо мати
F(x)
z
z12=z z2 = (z1+z2)z2 = z1z2 + z22;
z1
z2
z1z2 + z22 - z12 = 0,
звідки =.
а
x
b
x
Знайти F(х)...
